The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
In computer networks such as the Internet, packets of data are sent from a source to a destination via a network of elements including links (communication paths such as telephone or optical lines) and nodes (for example, routers directing the packet along one or more of a plurality of links connected to it) according to one of various routing protocols.
One class of routing protocol is the link state protocol. The link state protocol relies on a routing algorithm resident at each node. Each node on the network advertises, throughout the network, links to neighboring nodes and provides a cost associated with each link, which can be based on any appropriate metric such as link bandwidth or delay and is typically expressed as an integer value. Based on the advertised information in the form of a link state packet (LSP) each node constructs a link state database (LSDB), for which a map of the entire network topology can be constructed, and from that constructs generally a single optimum route to each available node based on an appropriate algorithm such as, for example, a shortest path first (SPF) algorithm. As a result a “spanning tree” (SPT) is constructed, rooted at the node and showing an optimum path including intermediate nodes to each available destination node. The results of the SPF are stored in a routing information base (RIB) and based on these results the forwarding information base (FIB) or forwarding table is updated to control forwarding of packets appropriately. When there is a network change an LSP representing the change is flooded through the network by each node adjacent the change, each node receiving the LSP sending it to each adjacent node.
In normal forwarding each node decides, irrespective of the node from which it received a packet, the next node to which the packet should be forwarded. In some instances this can give rise to a “loop”. In particular this can occur when the databases (and corresponding forwarding information) are temporarily de-synchronized during a routing transition, that is, where because of a change in the network, a new LSP is propagated that induces creating a loop in the RIB or FIB. This can continue for as long as the loop remains although usually the packet will have a maximum hop count after which it will be discarded. Such a loop can be a direct loop between two nodes or an indirect loop around a circuit of nodes.
In some networks, two or more links are logically associated in a shared risk link group (SRLG). If a first link in an SRLG fails, all other links in the SRLG are considered to be failed as well, in determining a repair path around the first failed link.
IP fast re-routing (IPFRR) is an initiative in the Internet Engineering Task Force to develop techniques for rapidly constructing repair paths around a failed link, a failed node, or a predictable failure of an SRLG. However, known solutions do not provide protection against the failure of multiple links at approximately the same time where the links are not members of a known SRLG. A particular problem in this context is that the repair for one of the links may attempt to traverse the second failure. If the repair for that failure happens to traverse the first link, then a looping repair path results, which cannot deliver the packets to their destination. To avoid this problem, known not-via IPFRR approaches specifically forbid the repair of an already repaired packet in order to prevent such loops. However, this constraint only reduces the collateral damage caused by the loop, and does not of itself allow the packet to be delivered to its destination.